package com.kevin.Code.SlidingWindow;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

/**
 * @author Vinlee Xiao
 * @Classname MinimumWindowSubstring
 * @Description Leetcode 76. 最小覆盖子串 难度 困难 没啥思路
 * @Date 2021/10/22 19:43
 * @Version 1.0
 */
public class MinimumWindowSubstring {

    HashMap<Character, Integer> sHashMap = new HashMap<>();
    HashMap<Character, Integer> tHashMap = new HashMap<>();

    /**
     * @param s
     * @param t
     * @return
     */
    public String minWindow(String s, String t) {

        int sLen = s.length();
        int tLen = t.length();

        if (sLen < tLen) {
            return "";
        }

        char[] sCharArray = s.toCharArray();
        char[] tCharArray = t.toCharArray();

        //将字符串t中的字符都放入Hash表中
        for (int i = 0; i < tLen; i++) {
            Character word = tCharArray[i];
            tHashMap.put(word, tHashMap.getOrDefault(word, 0) + 1);
        }


        int left = 0;
        int right = -1;
        int minLen = sLen + 1;
        int subLeft = -1;
        int subRight = -1;

        while (right < sLen) {
            right++;

//            Character s1 = sCharArray[right];

            if (right < sLen && tHashMap.containsKey(sCharArray[right])) {
                sHashMap.put(sCharArray[right], sHashMap.getOrDefault(sCharArray[right], 0) + 1);

            }

            /**
             * 进行边界控制
             */
            while (check() && left <= right) {

                //新的子串长度是否小于原来的子串长度
                int currentLen = right - left + 1;
                if (currentLen < minLen) {
                    //更新最小的子串长度
                    minLen = currentLen;
                    //记录最最小包含子串的最左、最右坐标
                    subLeft = left;
                    subRight = right + 1;
                }

                Character s2 = sCharArray[left];
                if (tHashMap.containsKey(s2)) {
                    sHashMap.put(s2, sHashMap.get(s2) - 1);
                }
                left++;
            }
        }

//        System.out.println(subRight);
        return subLeft == -1 ? "" : s.substring(subLeft, subRight);

    }

    /**
     * 检查字串s是否包含子串t中的子串
     *
     * @return
     */
    private boolean check() {
        Set<Map.Entry<Character, Integer>> entrySet = tHashMap.entrySet();
        for (Map.Entry<Character, Integer> entry : entrySet) {
            Character key = entry.getKey();
            Integer value = entry.getValue();

            if (sHashMap.getOrDefault(key, 0) < value) {

                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        MinimumWindowSubstring minimumWindowSubstring = new MinimumWindowSubstring();
        String s = minimumWindowSubstring.minWindow("ADOBECODEBANC", "ABC");
        System.out.println(s);
//        System.out.println("a".substring(0,1));
    }
}
